import java.util.*;

public class Topk {
    /**
     * 求数组当中的前k个最小的值
     */
//    public static int[] topK(int[] array, int k) {
////        //创建一个大小为k的大根堆
////        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
////            @Override
////            public int compare(Integer o1, Integer o2) {
////                return o2-o1;
////            }
////        });
////        //遍历数组当中的元素，前k个元素放到队列当中
////        for (int i = 0; i < array.length; i++) {
////            if (maxHeap.size() < k){
////                maxHeap.offer(array[i]);
////            }else {
////                int top = maxHeap.peek();
////                if (top > array[i]){
////                    maxHeap.poll();
////                    maxHeap.offer(array[i]);
////            }
////            }
////
////        }
////        int[] tmp = new int[k];
////        for (int i = 0; i < k; i++) {
////            tmp[i] = maxHeap.poll();
////
////        }
////        return  tmp;
////    }
////
////    public static void main(String[] args) {
////        int[] array = {18,21,8,10,34,12};
////        int[] tmp = topK(array,3);
////        System.out.println(Arrays.toString(tmp));
//
//        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return o1 - o2;
//            }
//        });
//        //遍历数组当中的元素，前k个元素放到队列当中
//        for (int i = 0; i < array.length; i++) {
//            if (maxHeap.size() < k) {
//                maxHeap.offer(array[i]);
//            } else {
//                int top = maxHeap.peek();
//                if (top < array[i]) {
//                    maxHeap.poll();
//                    maxHeap.offer(array[i]);
//                }
//            }
//        }
//        int[] tmp = new int[k];
//        for (int i = 0; i < k; i++) {
//            tmp[i] = maxHeap.poll();
//
//        }
//        return tmp;
//
//
//        public List<List<Integer>> kSmallestPairs ( int[] nums1, int[] nums2, int k){
//            PriorityQueue<List<Integer>> maxHeap1 = new PriorityQueue<>(k, new Comparator<List<Integer>>() {
//                @Override
//                public int compare(List<Integer> o1, List<Integer> o2) {
//                    return (o2.get(0) + o2.get(1)) - (o1.get(0) + o1.get(1));
//                }
//            });
//            for (int i = 0; i < Math.min(nums1.length,k); i++) {
//                for (int j = 0; j < Math.min(nums2.length,k); j++) {
//                    if (maxHeap1.size() < k){
//                        List<Integer> tmplist = new ArrayList<>();
//                        tmplist.add(nums1[i]);
//                        tmplist.add(nums2[j]);
//                        maxHeap1.offer(tmplist);
//                    }else {
//                        int top = maxHeap1.peek().get(0) + maxHeap1.peek().get(1);
//                        if (top > nums1[i] + nums2[j]){
//                            maxHeap1.poll();
//                            List<Integer> tmplist = new ArrayList<>();
//                            tmplist.add(nums1[i]);
//                            tmplist.add(nums2[j]);
//                            maxHeap1.offer(tmplist);
//                        }
//                    }
//                }
//            }
//            List<List<Integer>> ret = new ArrayList<>();
//            for (int i = 0; i < k && maxHeap1.isEmpty(); i++) {
//                ret.add(maxHeap1.poll());
//            }
//            return ret;
//
//        }
//
//
//    }
//
//    public static void main(String[] args) {
//        int[] array = {18, 21, 8, 10, 34, 12};
//        int[] tmp = topK(array, 3);
//        System.out.println(Arrays.toString(tmp));
//    }
//}
    class Solution {
        public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            PriorityQueue<List<Integer>> minHeap = new PriorityQueue<>(k, new Comparator<List<Integer>>() {
                @Override
                public int compare(List<Integer> o1, List<Integer> o2) {
                    return(o2.get(0) + o2.get(1)) - (o1.get(0) + o1.get(1));
                }
            });
            for (int i = 0; i < Math.min(nums1.length,k); i++) {
                for (int j = 0; j < Math.min(nums2.length,k); j++) {
                    if (minHeap.size() < k){
                        List<Integer> list = new LinkedList<>();
                        list.add(nums1[i]);
                        list.add(nums2[j]);
                        minHeap.offer(list);
                    }else{
                        int top = minHeap.peek().get(0) + minHeap.peek().get(1);
                        if (top > nums1[i] + nums2[j]){
                            List<Integer> list = new LinkedList<>();
                            list.add(nums1[i]);
                            list.add(nums2[j]);
                            minHeap.offer(list);

                        }
                    }

                }

            }
            List<List<Integer>> ret = new ArrayList<>();
            for (int i = 0; i < k && minHeap.isEmpty(); i++) {
                ret.add(minHeap.poll());
            }
            return ret;


        }

    }
}

